module.exports = {
	TreeNode: function(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
	},
	/**
	 * 通过一个层次遍历的数组生成一棵二叉树
	 * @param {any[]} array
	 * @return {TreeNode}
	 */
	getTreeFromLayerOrderArray: function (array) {
		let n = array.length;
		if (!n) return null;
		let index = 0;
		let root = new TreeNode(array[index++]);
		let queue = [root];
		while(index < n) {
				let top = queue.shift();
				let value = array[index++];
				top.left = value == null ? null : new TreeNode(value);
				if (index < n) {
						let value = array[index++];
						top.right = value == null ? null : new TreeNode(value);
				}
				if (top.left) queue.push(top.left);
				if (top.right) queue.push(top.right);
		}
		return root;
	},
	/**
	 * 层序遍历一棵二叉树 生成一个数组
	 * @param {TreeNode} root 
	 * @return {any[]}
	 */
	getLayerOrderArrayFromTree: function(root) {
			let res = [];
			let que = [root];
			while (que.length) {
					let len = que.length;
					for (let i = 0; i < len; i++) {
							let cur = que.shift();
							if (cur) {
									res.push(cur.val);
									que.push(cur.left, cur.right);
							} else {
									res.push(null);
							}
					}
			}
			while (res.length > 1 && res[res.length - 1] == null) res.pop(); // 删掉结尾的 null
			return res;
	}
}